package org.example.myleet.p719;

import java.util.Arrays;

public class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int count = 0;
            for (int j = 0; j < n; ++j) {
                int i = binarySearch(nums, j, nums[j] - mid);
                count += j - i;
            }
            if (count >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    //寻找以num[j]为右侧的形成num[j] - num[i] >= mid的最小i
    private int binarySearch(int[] nums, int j, int target) {
        int l = 0, r = j;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}
